package leetcode.sort;

public class StateSort {
    public static void main(String[] args) {
        StateSort stateSort = new StateSort();
        int[] list = stateSort.creactMixStates(new int[]{
                7, 6, 4, 3, 5, 7, 4, 1, 2
        }, 9);

        int[] ints = stateSort.createArr();
        ints = stateSort.sort(ints);
        for (int a=0;a<ints.length;a++){
            System.out.print(" "+ints[a]);
        }
    }

    private int[] sort(int[] ints) {
        ints = creactMixStates(ints, ints.length);
        for (int a = ints.length - 1; a >= 0; a--) {
            int i = ints[a];
            ints[a] = ints[0];
            ints[0] = i;
            ints = creactMixStates(ints,a);
        }
        return ints;
    }

    private int[] createArr() {
        int[] ints = new int[20];
        for (int a = 0; a < ints.length; a++) {
            ints[a] = (int) (Math.random() * 10000);
        }
        return ints;
    }


    public int[] creactMixStates(int[] list, int length) {
        for (int index = length/2; index >= 0; index--) {
                rebuild(list, index, length);
        }
        return list;
    }

    private void rebuild(int[] list, int i, int length) {
        int nowValue = list[i];
        while (true) {
            int left = (i + 1) * 2 - 1;
            int right = (i + 1) * 2;
            int minIndex = getMinIndex(list, left, right, length);
            if (minIndex != -1 && nowValue > list[minIndex]) {
                list[i] = list[minIndex];
                i = minIndex;
            } else {
                list[i] = nowValue;
                return;
            }
        }
    }

    private int getMinIndex(int[] list, int left, int right, int length) {
        int leftValue = left < length ? list[left] : Integer.MAX_VALUE;
        int rightValue = right < length ? list[right] : Integer.MAX_VALUE;
        if (leftValue == Integer.MAX_VALUE) {
            return right < length ? right : -1;
        } else if (rightValue == Integer.MAX_VALUE) {
            return left;
        } else {
            return leftValue > rightValue ? right : left;
        }
    }
}